package com.demo.datastructure.reorder.countingSort;

import java.util.Random;

/**
 * @description: 计数排序
 * @author: ljr
 * @time: 2021/5/6 20:38
 */
public class MyCountingSort3 {

    public static void countingSort(int[] args, int n){
        if(n <= 1){ return;}

        int max = args[0];
        int min = args[0];
        int i = 1;
        for(; i < n; i++){
            if(args[i] > max){
                max = args[i];
                continue;
            }

            if(args[i] < min){
                min = args[i];
            }
        }

        int[] c = new int[max-min+1];
        for(i = 0; i < n; i++){
            c[args[i]-min]++;
        }

        for(i = 1; i < c.length; i++){
            c[i] = c[i]+c[i-1];
        }

        int[] tem = new int[n];
        for(i = n-1; i > -1; i--){
            int index = c[args[i]-min]-1;
            tem[index] = args[i];
            c[args[i]-min]--;

           /* if(i!= 0 && c[i] == c[i-1]){
                continue;
            }

            int num = 0;
            if(i == 0){
                num = c[i];
            }else{
                num = c[i]-c[i-1];
            }

            for(int l = 0; l < num; l++){
                args[m--] = i+min;
            }*/
        }

        for (i = 0; i < n; ++i) {
            args[i] = tem[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[10000000];
        Random random = new Random();
        for(int i = 0; i < nums.length; i++){
            nums[i] = random.nextInt(1000000);
        }

        long cu = System.currentTimeMillis();
        MyCountingSort.countingSort(nums,nums.length);
        System.out.println(System.currentTimeMillis()-cu);
    }
}
